§ 2.1 Field of the Invention
The present invention concerns the communication of data over networks, such as the Internet for example. More specifically, the present invention concerns scheduling the servicing (e.g., dispatching) of cells or packets buffered at input ports of a switch.
§ 2.2 Related Art
Switches and routers are used in networks, such as the Internet for example, to forward data towards its destination. The need for high-speed switches and routers is introduced in § 2.2.1 below. Then, input buffering, as used in high-speed switches, is introduced in § 2.2.2 below.
§ 2.2.1 The Need for Large-Scale and High-Speed (e.g., Terabit) Routers and Switches
Many expect that Internet traffic will continue to grow explosively. Given this assumption, it is expected that high-speed switches and routers (e.g., those having a throughput over one Terabit per second) will become necessary. Most high-speed packet switches adopt a fixed-size cell in the switch fabric. If variable length packets are to be supported in the network, such packets may be segmented and/or padded into fixed-sized cells upon arrival, switched through the fabric of the switch, and reassembled into packets before departure. Input buffering is introduced below in § 2.2.2 as a way to handle these incoming cells.
§ 2.2.2 Buffering in High-Speed Routers and Switches
There are various types of buffering strategies in switch architectures: input buffering, output buffering, or crosspoint buffering. Information on these strategies can be found in the following articles: G. Nong and M. Hamdi, “On the Provision of Quality-of-Service Guarantees for Input Queued Switches,” IEEE Commun. Mag., Vol. 38, No. 12, pp. 62–69 (December 2000); E. Oki, N. Yamanaka, Y. Ohtomo, K. Okazaki, and R. Kawano, “A 10-Gb/s (1.25 Gb/s×8) 4×2 0.25-micrometer CMOS/SIMOX ATM Switch Based on Scalable Distribution Arbitration,” IEEE J. Solid-State Circuits, Vol. 34, No. 12, pp. 1921–1934 (December 1999); and J. Turner and N. Yamanaka, “Architectural Choices in Large Scale ATM Switches,” IEICE Trans. Commun., Vol. E81-B, No. 2, pp. 120–137 (Feburary 1998). Each of these articles is incorporated herein by reference. Input buffering is a cost effective approach for high-speed switches. This is because input-buffered switches do not require internal speedup, nor do they allocate buffers at each crosspoint. They also relax memory-bandwidth and memory-size constraints.
§ 2.2.2.1 The Use of Virtual Output Queues to Avoid Head-of-Line Blocking
It is well known that head-of-line (“HOL”) blocking limits the maximum throughput (e.g., to 58.6%) in an input-buffered switch with a First-In-First-Out (FIFO) structure. See, e.g., the article, M. J. Karol, M. G. Hluchyj, and S. P. Morgan, “Input Versus Output Queuing on a Space-Division Packet Switch,” IEEE Trans. Commun., Vol. COM-35, pp. 1347–1356 (1987). This article is incorporated herein by reference. The article, N. Mckeown, “The iSLIP Scheduling Algorithm for Input-Queued Switches,” IEEE/ACM Trans. Networking, Vol. 7, No. 2, pp. 188–200 (April 1999), shows using a Virtual-Output-Queue (VOQ) structure to overcome HOL-blocking. This article is incorporated herein by reference.
In an input-buffered switch that uses VOQs, a fixed-size cell is sent from any input to any output, provided that, in a given time slot, no more than one cell is sent from the same input, and no more than one cell is received by the same output. Each input port has N VOQs, one for each of N output ports. The HOL cell in each VOQ can be selected for transmission across the switch in each time slot. Therefore, every time slot, a scheduler has to determine one set of matching. That is, for each of the output ports, the scheduler may match one of the corresponding VOQs with the output port.
§ 2.2.2.2 Maximum-Sized and Maximal-Sized Matching Algorithms in High Speed Switches 
Maximum-sized matching algorithms to schedule the input-output matching for input-buffered switches with VOQS, that achieve 100% throughput have been proposed. See, e.g., the articles: J. E. Hopcroft and R. M. Karp, “An Algorithm for Maximum Matching in Bipartite Graphs,” Soc. Ind. Appl. Math J. Computation, Vol. 2, pp. 225–231 (1973); and N. Mckeon, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% Throughput in Input-Queued Switches,” IEEE Trans. Commun., Vol. 47, No. 8, pp. 1260–1267 (August 1999). These articles are incorporated herein by reference. Unfortunately, these algorithms are hard to implement in high-speed switches because of their high computing time complexity.
Maximal-sized matching algorithms have been proposed as an alternative to the maximum-sized matching ones. Two of these algorithms, iSLIP and Dual Round-Robin Matching (DRRM), are described in the articles: N. Mckeown, “The iSLIP Scheduling Algorithm for Input-Queued Switches,” IEEE/ACM Trans. Networking, Vol. 7, No. 2, pp. 188–200 (April 1999); H. J. Chao and J. S. Park, “Centralized Contention Resolution Schemes for a Large-Capacity Optical ATM Switch,” Proc. IEEE ATM Workshop '97, Fairfax, Va. (May 1998); and H. J. Chao, “Saturn: A Terabit Packet Switch Using Dual Round-Robin,” IEEE Commun. Mag., Vol. 38, No. 12, pp. 78–84 (December 2000). These articles are incorporated herein by reference. The computing complexity of the iSLIP and DRRM methods are less than maximum matching methods. Moreover, the iSLIP and DRRM methods provide 100% throughput under uniform traffic and complete fairness for best-effort traffic.
§ 2.2.2.2.1 DRRM and its Performance
A dual round-robin matching arbitration process is described in U.S. patent application Ser. No. 09/312.320, entitled “METHODS AND APPARATUS FOR ARBITRATING OUTPUT PORT CONTENTION IN A SWITCH HAVING VIRTUAL OUTPUT QUEUING”, filed on May 14, 1999 and listing Hung-Hsiang Jonathan Chao and Jin-Soo Park as inventors. This patent application is incorporated herein by reference. In an exemplary embodiment of the DRRM scheme, each input port maintains N VOQs. The DRRM process has two steps—a request step and a grant step. In the request step, each input sends an output request corresponding to the first nonempty VOQ in a fixed round-robin order, staring from the current position of the pointer. The pointer remains at that nonempty VOQ if the selected output is not granted in the grant step (described below). The pointer of the input arbiter is incremented by one location beyond the selected output if, and only if, the request is granted in the grant step.
In the grant step, if an output receives one or more requests, it chooses the one that appears next in a fixed round-robin schedule starting from the current position of the pointer. The output notifies each requesting input whether or not its request was granted. The pointer of the output arbiter is incremented to one location beyond the granted input. If there are no requests, the pointer remains where it is.
The performance of the DRRM scheme has been shown and compared with that of ISLIP in the article, Y. Li, S. Panwar, H. J. Chao, “On the performance of a Dual Round-Robin switch,” IEEEINFOCOM 2001, vol 3, pp. 1688–1697, April 2001. Under uniform and i.i.d. traffic the throughput of a DRRM switch is 100%, and the average cell delay increases with switch size for a given load. The performance under nonuniform traffic is also considered in the article, Y. Li, S. Panwar, H. J. Chao, “On the performance of a Dual Round-Robin switch,” IEEEINFOCOM 2001, vol 3, pp. 1688–1697, April 2001. Simulation results show that under the hot-spot traffic, throughput for the hot-spot output of a DRRM switch is 100%. However, for nonuniform traffic scenarios, simulations show that the throughput of both DRRM and iSLIP drops below 100%.
§ 2.2.3 Average Packet Delay
Most of the previous work only considers the cell delay that a cell suffers from the time it enters a VOQ to the time it is transferred to the destination output port. Additional delay incurred at the Output Reassembly Module (“ORM”) of each output to reassemble packets (See the article, M. Am Marsan, A. Bianco, P. Giaaccone, E. Leonardi, F. Neri, “Packet Scheduling in Input-Queued Cell-Based Switches,” IEEEINFOCOM 2001, vol. 2 PP. 1085–1094, April, 2001.). Multiple queues are needed at each ORM if cells belonging to different packets are interleaved at the same output. When a cell is transferred through the switch fabric to the output, it is delivered to one of the queues of the ORM. The cells belonging to the same packet will be delivered to the same queue and can only leave the queue until the whole packet is reassembled. The total delay a packet suffers includes the cell delay and the time needed for reassembly. Thus the cell delay is not enough to evaluate the variable component of the delay incurred in a packet switch.
Since real world traffic may often be non-uniform, a better arbitration technique is needed. Such an arbitration technique should not be too complex and should perform reasonably well for various traffic scenarios. Further, such an arbitration technique should have an acceptable average packet delay.